use std::{borrow::BorrowMut, cell::RefCell};

#[derive(Debug)]
pub enum Tree {
    Node(Box<Tree>, i32, Box<Tree>),
    None,
}

#[derive(Debug, PartialEq)]
pub enum TreeIterOrder {
    Head,
    Mid,
    Tail,
}

impl Tree {
    pub fn new() -> Box<Tree> {
        Box::new(Self::None)
    }
    pub fn insert(&mut self, num: i32) {
        match self {
            Self::Node(l, val, r) => {
                if num < *val {
                    l.insert(num);
                } else {
                    r.insert(num);
                }
            }
            Self::None => *self = Self::Node(Box::new(Self::None), num, Box::new(Self::None)),
        }
    }

    pub fn iter_to_vec(&self, e: TreeIterOrder) -> Vec<i32> {
        let mut vc = vec![];
        Self::inner_recursive(&e, self, &mut vc);
        vc
    }

    fn inner_recursive(e: &TreeIterOrder, tr: &Tree, vc: &mut Vec<i32>) {
        match tr {
            Tree::None => {}
            Tree::Node(l, val, r) => {
                if TreeIterOrder::Head == *e {
                    vc.push(*val);
                }
                Self::inner_recursive(e, l, vc);
                if TreeIterOrder::Mid == *e {
                    vc.push(*val);
                }
                Self::inner_recursive(e, r, vc);
                if TreeIterOrder::Tail == *e {
                    vc.push(*val);
                }
            }
        }
    }
}

#[test]
pub fn tree_node() {
    let mut tree = Tree::new();
    for x in (0..12).rev() {
        tree.insert(x);
    }
    println!("{:?}", tree.iter_to_vec(TreeIterOrder::Head));
    println!("{:?}", tree.iter_to_vec(TreeIterOrder::Mid));
    println!("{:?}", tree.iter_to_vec(TreeIterOrder::Tail));
    println!("{tree:?}");

    fn inner_build(nums: &Vec<i32>, l: i32, r: i32) -> Box<Tree> {
        if l > r {
            return Box::new(Tree::None);
        }
        let m = (l + r) / 2;
        let mut tr = Box::new(Tree::Node(
            Box::new(Tree::None),
            nums[m as usize],
            Box::new(Tree::None),
        ));
        if let Tree::Node(left, _, right) = tr.as_mut() {
            *left = inner_build(nums, l, m - 1);
            *right = inner_build(nums, m + 1, r);
        }
        tr
    }

    let vc = vec![-10, -9, 0, 1, 4];
    println!("{:?}", inner_build(&vc, 0, (vc.len() - 1) as i32))
}

#[test]
pub fn test() {
    let mut v = std::rc::Rc::new(RefCell::new(1));
    let mut val = v.borrow();
}
